package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/02/01 11:27
 **/

import java.util.HashSet;
import java.util.Set;

/**
 * 题目 ：无重复字符的最长子串
 * 题目详述 ：
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class LengthOfLongestSubstring02 {
    /**
     * 思路 ：
     * 滑动窗口实现 ：即，双指针分别指向无重复子串的首元素，尾元素;
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        //左右指针，分别指向截取子串的首元素 && 尾元素
        int p1 = 0;
        int p2 = 0;
        int len = s.length();
        int maxLength = 0;
        // 即，while循环结束条件 ：p1左指针到达字符串s的尾元素
        while(p1 < len){
            // 隐性条件 ：左指针 < 右指针
            if (p1 < p2){
                set.remove(s.charAt(p1));
                p1++;
            }
            // 右指针 < len && 当前所截取的子串为无重复子串;
            // 直至右指针指向重复字符;
            while(p2 < len && !set.contains(s.charAt(p2))){
                set.add(s.charAt(p2));
                p2++;
            }
            maxLength = Math.max(maxLength , p2 - p1);
        }
        return maxLength;
    }
    /**
     * 时间复杂度 ：O（n）;(由于左右指针都会对于字符串进行依次遍历)
     * 空间复杂度 ：O（k）;（k,取决于最长无重复子串的长度;）
     */
}
